package com.wtgroup.demo.leetcode.q020;

import java.util.*;

/**
 * 栈
 *
 * @author dafei
 * @version 0.1
 * @date 2021/4/4 13:18
 */
public class S_LC_M1 {

    public static void main(String[] args) {
        String[] inputs = {"()", "()[]{}", "(]", "([)]", "{[]}"};
        S_LC_M1 exe = new S_LC_M1();
        for (String input : inputs) {
            System.out.println(exe.isValid(input));
        }
    }

    static Map<Character, Character> mapping = new HashMap<>();
    static {
        mapping.put('(', ')');
        mapping.put('[', ']');
        mapping.put('{', '}');
    }

    public boolean isValid(String s) {

        Deque<Character> stack = new LinkedList<Character>();
        for (Character c : s.toCharArray()) {
            // 右括号: 弹栈比较
            if (!mapping.containsKey(c)) {
                if (stack.isEmpty() || !c.equals(mapping.get(stack.pop()))) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }

        // !! 最后队列不为空, 才可以 !!
        // 最后只有一堆左括号或一堆有括号, 最后队列都不为空
        return stack.isEmpty();
    }
}
